package com.wfm.leetcode.editor.cn;

import java.util.PriorityQueue;

/**
 * 用优先队列，先放进去k个元素，然后再放剩下的元素，然后每次取队列头的时候，需要判断是否在窗口范围内。
 * 时 o(nlogn) n是nums的长度，logn是堆插入一个数据的时间复杂度
 * 空 o(n) 就是优先队列的空间
 *
 * i-k+1的来由  比如k=3
 * 1  2  3  4  5  6  7  8  9
 *       |     |
 *    i-k+1    i
 *
 * 不能用双指针，因为比如9,4,5 7 6 1 第一个窗口最大值9，第二个窗口最大值是7
 * 最开始想的是ij指针维持k=3的窗口，比如第一个窗口最大值max是9，然后移动窗口，比较max和新的7，但是发现max=9已经移出窗口了。该方案不行。
 * 如果是求总和的最大值，那么可以用这个方案
 */
public class PTwo39滑动窗口最大值{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 构建优先队列，放进去k个元素
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)-> o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1]);
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i],i});
        }
        int[] ans = new int[n-k+1];
        // 堆头就是最大值
        ans[0] = pq.peek()[0];
        // 遍历剩下的元素
        for (int i = k; i < n; i++) {
            // 加入元素
            pq.offer(new int[]{nums[i],i});
            // 判断堆顶元素是否在窗口内，不在则删除
            while (pq.peek()[1]<i-k+1){
                pq.poll();
            }
            // 堆顶就是最大值
            ans[i-k+1]=pq.peek()[0];
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PTwo39滑动窗口最大值().new Solution();
    }
}